『詳説 データベース』

https://gyazo.com/86828ccb691f013c2fad20b76b2baf62

2021/7出版

監訳者まえがき

はじめに

第I部　ストレージエンジン

I.1　データベースの比較

I.2　トレードオフの理解

1章　基本事項の紹介と概要

1.1　DBMSアーキテクチャ

1.2　メモリベースのDBMSとディスクベースのDBMS

1.2.1　メモリベースのストアの永続性

1.3　列指向DBMSと行指向DBMS

1.3.1　行指向のデータレイアウト

1.3.2　列指向のデータレイアウト

1.3.3　相違点と最適化

1.3.4　ワイドカラムストア

1.4　データファイルとインデックスファイル

1.4.1　データファイル

1.4.2　インデックスファイル

1.4.3　間接参照としてのプライマリインデックス

1.5　バッファリングとイミュータビリティおよびオーダリング

1.6　まとめ

2章　Bツリーの基本

2.1.1　ツリーのバランシング

2.1.2　ディスクベースのストレージ用のツリー

2.2　ディスクベースの構造

2.2.1　ハードディスクドライブ

2.2.2　ソリッドステートドライブ

2.2.3　ディスク上の構造

2.3　ユビキタスBツリー

2.3.1　Bツリーの階層

2.3.2　セパレータキー

2.3.3　Bツリーの検索の計算量

2.3.4　Bツリーの検索アルゴリズム

2.3.5　キーのカウント

2.3.6　Bツリーノードの分割

2.3.7　Bツリーノードのマージ

2.4　まとめ

3章　ファイルフォーマット

3.1　モチベーション

3.2　バイナリエンコーディング

3.2.1　プリミティブな型

3.2.2　文字列と可変長のデータ

3.2.3　ビットパック化データ：ブール型と列挙型とフラグ

3.3　一般的な原則

3.4　ページ構造

3.5　スロット化ページ

3.6　セルのレイアウト

3.7　セルをスロット化ページに結合

3.8　可変長データの管理

3.9　バージョン管理

3.10　チェックサム

3.11　まとめ

4章　Bツリーの実装

4.1　ページヘッダ

4.1.1　マジックナンバー

4.1.2　兄弟（Sibling）リンク

4.1.3　右端のポインタ

4.1.4　ノードハイキー（NodeHighKey）

4.1.5　オーバーフローページ

4.2　二分探索

4.2.1　間接ポインタによる二分探索

4.3　スプリットとマージの伝播

4.3.1　パンくずリスト

4.4　リバランシング

4.5　右側限定の追加

4.5.1　バルクロード

4.6　圧縮

4.7　バキュームとメンテナンス

4.7.1　更新と削除による断片化

4.7.2　ページのデフラグ

4.8　まとめ

5章　トランザクション処理とリカバリ

5.1　バッファ管理

5.1.1　キャッシュの概要

5.1.2　キャッシュの退避

5.1.3　キャッシュにおけるページのロック

5.1.4　ページの置換

5.2　リカバリ

5.2.1　ログの概要

5.2.2　操作とデータログ

5.2.3　stealポリシーとforceポリシー

5.2.4　ARIES

5.3　同時実行制御

5.3.1　直列化可能性

5.3.2　トランザクションの分離

5.3.3　読み取りと書き込みのアノマリー

5.3.4　分離レベル

5.3.5　楽観的同時実行制御

5.3.6　マルチバージョン同時実行制御

5.3.7　悲観的同時実行制御

5.3.8　ロックベースの同時実行制御

5.4　まとめ

6章　Bツリーの亜種

6.1　コピーオンライト

6.1.1　コピーオンライトの実装：LMDB

6.2　ノード更新の抽象化

6.3.1　WiredTiger

6.3.2　遅延適応ツリー

6.4.1　フラクショナルカスケーディング

6.4.2　対数的な配列

6.5.1　アップデートチェーン

6.5.2　コンペアアンドスワップによる同時実行性の制御

6.5.3　構造を変更する操作

6.5.4　統合とガベージコレクション

6.6.1　vanEmdeBoasレイアウト

6.7　まとめ

7.1.1　LSMツリー構造

7.1.2　更新と削除

7.1.3　LSMツリーの検索

7.1.4　マージイテレーション

7.1.5　調停

7.1.6　LSMツリーにおけるメンテナンス

7.2　読み取りと書き込みおよび領域の増幅

7.3　実装の詳細

7.3.5　圧縮

7.4　順序付けされないLSMストレージ

7.4.1　Bitcask

7.4.2　WiscKey

7.5　LSMツリーにおける並行性

7.6　ログスタック

7.6.1　フラッシュトランスレーションレイヤ

7.6.2　ファイルシステムログ

7.7　LLAMAと注意深いスタック

7.7.1　Open-ChannelSSD

7.8　まとめ

第Ⅰ部　むすび

第II部分散システム

II.1　基本的な定義

8章　基本事項の紹介と概要

8.1　並行実行

8.1.1　分散システムでの共有された状態

8.2　分散コンピューティングの誤謬

8.2.1　プロセス

8.2.2　クロックと時間

8.2.3　状態の一貫性

8.2.4　ローカル実行とリモート実行

8.2.5　障害への対処の必要性

8.2.6　ネットワーク分断と部分障害

8.2.7　カスケード障害

8.3　分散システムの抽象化

8.3.1　リンク

8.4　 2人の将軍の問題

8.5　FLPの不可能性

8.6　システムの同期性

8.7　障害モデル

8.7.1　クラッシュ障害

8.7.2　欠落障害

8.7.3　任意障害

8.7.4　障害の処理

8.8　まとめ

9章　障害検出

9.1　ハートビートとping

9.1.1　タイムアウトフリーな障害検出機能

9.1.2　ハートビートのアウトソーシング

9.2　Phi-AccuralFailureDetector

9.3　ゴシップと障害検出

9.4　障害検出の問題記述の反転

9.5　まとめ

10章　リーダー選出

10.1　ブリーアルゴリズム

10.2　次候補へのフェイルオーバー

10.3　候補者／一般人の最適化

10.4　招待アルゴリズム

10.5　リングアルゴリズム

10.6　まとめ

11.1　可用性の実現

11.2.1　注意が必要なCAPの使用

11.2.2　収穫と収量

11.4　オーダリング

11.5　一貫性モデル

11.5.1　厳密な一貫性

11.5.2　線形化可能性

11.5.3　逐次一貫性

11.5.4　因果一貫性

11.6　セッションモデル

11.7　結果整合性

11.8　調整可能な一貫性

11.9　ウィットネスレプリカ

11.10　強力な結果整合性とCRDTs

11.11　まとめ

12.1　読み取り修復

12.2　ダイジェスト読み取り

12.6　ゴシップの散布

12.6.1　ゴシップの仕組み

12.6.2　オーバーレイネットワーク

12.6.4　部分的なビュー

12.7　まとめ

13章　分散トランザクション

13.1　アトミックに見せる操作

13.2.1　2PCにおけるコホートの障害

13.2.2　2PCにおけるコーディネータの障害

13.3.1　3PCにおけるコーディネータの障害

13.4　Calvinによる分散トランザクション

13.5　Spannerによる分散トランザクション

13.6　データベースパーティショニング

13.6.1　コンシステントハッシュ法

13.7　Percolatorによる分散トランザクション

13.8　調整の回避

13.9　まとめ

14章　合意

14.2　アトミックブロードキャスト

14.3.1　Paxosアルゴリズム

14.3.2　Paxosにおけるクォラム

14.3.3　障害シナリオ

14.3.4　Multi-Paxos

14.3.5　Fast Paxos

14.3.6　Egalitarian Paxos

14.3.7　Flexible Paxos

14.3.8　合意の汎用ソリューション

14.4.1　Raftにおけるリーダーの役割

14.4.2　障害シナリオ

14.5.2　リカバリとチェックポイント

14.6　まとめ

第Ⅱ部　むすび

付録A　参考文献

索引